package leetcode.每日一题;

import org.junit.Test;

import java.util.*;

/**
 * @author ：zsy
 * @date ：Created 2022/3/8 14:09
 * @description：https://leetcode-cn.com/problems/plates-between-candles/
 */
public class 蜡烛之间的盘子 {
    @Test
    public void test() {
        Solution solution = new Solution();
        System.out.println(Arrays.toString(
                solution.platesBetweenCandles(
                        "**|**|***|",
                        new int[][]{{2,5}, {5,9}})));
    }

    /*class Solution {
        public int[] platesBetweenCandles(String s, int[][] queries) {
            List<Integer> list = new ArrayList<>();
            char[] chars = s.toCharArray();
            for (int i = 0; i < chars.length; i++) {
                if (chars[i] == '|') {
                    list.add(i);
                }
            }
            int[] ans = new int[queries.length];
            int size = list.size();
            if (size == 0) {
                return ans;
            }
            int[] nums = new int[size];
            for (int i = 0; i < size; i++) {
                nums[i] = list.get(i);
            }
            int index = 0;
            for (int[] query : queries) {
                int left = query[0];
                int right = query[1];
                int leftCandleIdx = binary_search0(nums, left);
                int rightCandleIdx = binary_search1(nums, right);
                if (leftCandleIdx == -1
                        || rightCandleIdx == -1
                        || nums[rightCandleIdx] <= nums[leftCandleIdx]) {
                    ans[index++] = 0;
                    continue;
                }
                int candleNum = nums[rightCandleIdx] + 1 - nums[leftCandleIdx]
                        - (rightCandleIdx + 1 - leftCandleIdx);
                ans[index++] = Math.max(0, candleNum);
            }
            return ans;
        }

        private int binary_search0(int[] nums, int tar) {
            int l = 0;
            int r = nums.length - 1;
            while (l < r) {
                int mid = l + r >> 1;
                if (nums[mid] < tar) {
                    l = mid + 1;
                } else {
                    r = mid;
                }
            }
            return nums[r] >= tar ? r : -1;
        }

        private int binary_search1(int[] nums, int tar) {
            int l = 0;
            int r = nums.length - 1;
            while (l < r) {
                int mid = l + r + 1 >> 1;
                if (nums[mid] <= tar) {
                    l = mid;
                } else {
                    r = mid - 1;
                }
            }
            return nums[l] <= tar ? l : -1;
        }
    }*/

    class Solution {
        public int[] platesBetweenCandles(String s, int[][] queries) {
            int n = s.length();
            int len = queries.length;
            int[] preSum = new int[n];
            int[] left = new int[n];
            int[] right = new int[n];
            char[] chars = s.toCharArray();
            int l = -1;
            int r = -1;
            int sum = 0;
            for (int i = 0; i < chars.length; i++) {
                if (chars[i] == '*') {
                    sum++;
                } else {
                    l = i;
                }
                preSum[i] = sum;
                left[i] = l;
            }
            for (int i = n - 1; i >= 0; i--) {
                if (chars[i] == '|') {
                    r = i;
                }
                right[i] = r;
            }
            int[] ans = new int[len];
            int idx = 0;
            for (int[] query : queries) {
                int x = right[query[0]];
                int y = left[query[1]];
                ans[idx++] = x == -1 || y == -1 || x >= y ? 0 : preSum[y] - preSum[x];
            }
            return ans;
        }
    }
}
